package LeetcodeHot100;

import java.util.HashMap;
import java.util.Map;

/**
 * 无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 */
public class LengthOfLongestSubstring {
    //滑动窗口的思想
    //将不重复的字母存放在map集合中，key值为字符，value值为字符位置加一，加一表示从字符位置后一位开始不重复的
    //根据遍历结果，遇见相同的字符之后就更新子串区间
    public int lengthOfLongestSubstring(String s) {
         //存放结果集
         int ret=0;
         //遍历字符串
        Map<Character,Integer> map=new HashMap<>();
        for (int end = 0,start=0; end <s.length() ; end++) {
            char ch=s.charAt(end);
            //如果遇到了重复的字符
            if (map.containsKey(ch)){
                //就更新子串start的位置
                start=Math.max(map.get(ch),start);
            }
            //无论如何，都判断一下当前的结果和子串的长度
            ret=Math.max(ret,end-start+1);
            //遇到了不重复的字符就放进map集合中
            map.put(s.charAt(end),end+1);
        }
        return ret;
    }
}
